/**
 * 
 * 动态规划相关的题怎么解，主要看状态的定义。上面我们定义的是二维数组，这里我们 还可以定义一个三维数组。
 *      定义dp[i][j][k]表示在第i天交易结束后，最多进行j次交易所获得的最大利润。注意这 里的k要么是0，要么是1。0表示手里没有股票，1表示手里有一支股票。
 *        1.dp[i][j][0]：表示第i天交易结束之后，最多进行j次交易，并且手里 没有 股票的最大利润。
 *        2.dp[i][j][1]：表示第i天交易结束之后，最多进行j次交易，并且手里 持有 股票的最大利润。
 * 
 * 那么在当天结束之后我们会有6种状态
 *      1.没有进行过任何交易，利润永远为0
 *          dp[i][0][0]=0
 *      2.卖出过一次股票（完成一次交易），但目前手上没有股票：可能是今天卖出，也可 能是之前卖的（注意：买一次卖一次才能算一次完整的交易）
 *          dp[i][1][0]=max(dp[i-1][0][1]+prices[i],dp[i-1][1][0])
 *      3.卖出过两次股票（完成两次交易），但目前手上没有股票：也可能是今天卖的，也可能是之前卖的。
 *          dp[i][2][0]=max(dp[i-1][1][1]+prices[i],dp[i-1][2][0])
 *      4.没有卖出过任何股票，但目前手上持有股票：可能是今天持有的，也可能是之前持 有的
 *          dp[i][0][1]=max(dp[i-1][0][0]-prices[i],dp[i-1][0][1])
 *      5.卖出过一次股票（完成一次交易），但目前手上持有股票：可能是今天持有的，也 可能是之前持有的
 *          dp[i][1][1]=max(dp[i-1][1][0]-prices[i],dp[i-1][1][1])
 *      6.卖出过两次次股票（完成两次交易），但目前手上持有股票：由于最多交易2次， 这种情况是无效的
 *          dp[i][2][1]：无效
 * 
 *  有了上面的递推公式，我们再来看一下base case，第一天的时候我们要么买一支股 票，要么什么也不做，所以
 *      dp[0][0][0] = 0;  第一天没进行任何买卖 
 *      dp[0][0][1] = -prices[0];  第一天买入一支股票 
 *      第一天不可能有下面4种情况，所以是无效的 
 *          dp[0][1][0] = Integer.MIN_VALUE / 2; 
 *          dp[0][1][1] = Integer.MIN_VALUE / 2; 
 *          dp[0][2][0] = Integer.MIN_VALUE / 2; 
 *          dp[0][2][1] = Integer.MIN_VALUE / 2;
 * 
 * */

function maxProfit(prices) {
    var dp = [];
    for (let i = 0; i < prices.length; i++) {
        dp[i] = [];
        for (let j = 0; j < 3; j++) {
            dp[i][j] = [];
            for (let k = 0; k < 2; k++) {
                dp[i][j][k] = Number.MIN_VALUE;
            }
        }
    }

    dp[0][0][0] = 0; // 第一天没有买卖
    dp[0][0][1] = -prices[0]; // 第一天买入
    dp[0][1][0] = Number.MIN_VALUE / 2;
    dp[0][1][1] = Number.MIN_VALUE / 2;
    dp[0][2][0] = Number.MIN_VALUE / 2;
    dp[0][2][1] = Number.MIN_VALUE / 2;

    for (let i = 1; i < prices.length; i++) {
        dp[i][1][0] = Math.max(dp[i - 1][0][1] + prices[i], dp[i - 1][1][0]);
        dp[i][2][0] = Math.max(dp[i - 1][1][1] + prices[i], dp[i - 1][2][0]);
        dp[i][0][1] = Math.max(dp[i - 1][0][0] - prices[i], dp[i - 1][0][1]);
        dp[i][1][1] = Math.max(dp[i - 1][1][0] - prices[i], dp[i - 1][1][1]);
        //dp[i][2][1]：无效
    }

    //要么没交易，要么交易一次，要么交易两次，取最大值即可
    return Math.max(dp[prices.length - 1][0][0], Math.max(dp[prices.length - 1][1][0],
        dp[prices.length - 1][2][0]));
}

// 上面的三维数组我们还可以使用4个变量来表示，下面有详细注释，具体可以看下
// function maxProfit(prices) {
//     //类似于dp[i][0][1]，第一次买
//     var buy1 = Number.MIN_VALUE / 2;
//     //类似于dp[i][1][0]，第一次卖
//     var sell1 = 0;
//     //类似于dp[i][1][1]，第二次买
//     var buy2 = Number.MIN_VALUE / 2;
//     //类似于dp[i][2][0]，第二次卖
//     var sell2 = 0;
//     for (let i = 0; i < prices.length; i++) {
//         //递推公式
//         sell1 = Math.max(buy1 + prices[i], sell1);
//         sell2 = Math.max(buy2 + prices[i], sell2);
//         buy1 = Math.max(-prices[i], buy1);
//         buy2 = Math.max(sell1 - prices[i], buy2);
//     }
//     //要么没交易，要么交易一次，要么交易两次，取最大值即可
//     return Math.max(0, Math.max(sell1, sell2));
// }   